package Alibaba;

/**
 * @author zhangmin
 * @create 2022-01-20 9:57
 *
 * 62. 不同路径
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 * 1、回溯：路径：已选择的路径
 * 选择列表：选择向下或者向右
 * 终止条件：到达边界或者到右下角
 * 2、dp:dp[i][j]=dp[i-1][j]+dp[i][j-1]
 * 3、排列组合：需要移动 m+n-2次，其中有 m-1次向下移动，n-1次向右移动，
 *    因此路径的总数，就等于从 m+n-2 次移动中选择 m-1 次向下移动的方案数：
 *    (m+n-2)(m+n-3)..n/(m-1)!=（m+n-2）！/(m-1)!(n-1)!
 */
public class uniquePaths62 {

    int pathNum=0;
    void getPath(int m,int n,int i,int j){
        if (i<0||j<0||i>=m||j>=n)return;
        if (i==m-1&&j==n-1){
            pathNum++;
            return;
        }
        //作出选择
        getPath(m,n,i+1,j);
        getPath(m,n,i,j+1);
    }

    public int uniquePaths1(int m, int n) {
        getPath(m,n,0,0);
        return pathNum;
    }
    public int uniquePaths(int m, int n) {
        long res=1;
        for (int i = n,j=1; j < m; i++,j++) {
            res=res*i/j;
        }
        return (int)res;
    }
}
